package 剑指offer.链表;

/**
 * 一条链表，给一个头结点指针，一个某节点指针，删除某节点指针指向的数据
 * <p>
 * 最直接的办法，头结点往后遍历的某节点指针，然后删除某节点指针指向的节点
 * <p>
 * 很好的办法：
 * 头节点是一个幌子，若不是删除最后一个节点永远也不需要头节点帮忙
 * 办法就是：直接将某节点指针后面的数据复制给他自己，然后删除后面的节点
 */
public class 第18题删除链表的节点 {

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    // 删除链表中 point 指向的节点
    public static ListNode delNode(ListNode head, ListNode point) {
        if (head == null || point == null)
            return null;
        if (point.next == null) {
            point = null;
            return head;
        }
        if (head == point) {
            head = null;
            point = null;
            return head;
        }
        ListNode tmp = point.next;
        point.val = tmp.val;
        point.next = tmp.next;

        return head;
    }

    // 删除链表中的重复节点
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null)
            return pHead;
        // Java 里面没有引用传递，需要自己构造链表返回
        ListNode head = new ListNode(0);
        head.next = pHead;
        ListNode pre = head;
        ListNode cur = pre.next;
        while (cur != null) {
            // 防止空指针异常
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return head.next;
    }
}
